#leetcode题目42：接雨水
#难度：困难
#时间复杂度：O(n)
#空间复杂度：O(1)
#方法：双指针


#具体实现
#1.初始化两个指针，left和right，分别指向数组的开始和结束
#2.计算当前两个指针所指向的元素的面积，即(right - left) * min(height[right], height[left])
#3.更新最大面积
#4.移动指针，如果左指针小于右指针，则移动左指针，否则移动右指针
#5.返回最大面积

#关键思路\公式：每个位置所装雨水 = min（它左边最高的，它右边最高的）- 该位置本身高度
from typing import List

class Solution:
    #ai解法，但感觉这种更好理解
    # def trap(self,height:List[int]):
    #     res = 0
    #     left = 0
    #     right = len(height) - 1
    #     left_max = height[left]
    #     right_max = height[right]
    #     while left < right:
    #         #易错点：在循环里记得更新两边分别的最大值
    #         left_max = max(left_max,height[left])
    #         right_max = max(right_max, height[right])
    #         #谁小的话，那侧就可以安全地算res，因此就用那个索引处的max和height【】
    #         if left_max <= right_max:
    #             res += left_max - height[left]
    #             left += 1
    #         else:
    #             res += right_max - height[right]
    #             right -= 1

    #     return res

    #视频解法
    def trap(self,height:List[int]):
        ans=0
        stack=[]
        for i in range(len(height)):
            while stack and height[i]>height[stack[-1]]:
                top=stack.pop()
                if not stack:
                    break
                w=i-stack[-1]-1
                h=min(height[i],height[stack[-1]])-height[top]
                ans+=w*h
            stack.append(i)
        return ans

#测试数据
height = [0,1,0,2,1,0,1,3,2,1,2,1]
#预期输出：6
solution=Solution()
print(solution.trap(height))


height = [4,2,0,3,2,5]
#预期输出：9
solution=Solution()
print(solution.trap(height))